package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * binay
 * 2560. 打家劫舍 IV
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/6 16:59
 */
public class MinCapability {

    public static void main(String[] args) {
        MinCapability test = new MinCapability();

        // 5
//        int[] nums = {2, 3, 5, 9};
//        int k = 2;

        // 2
//        int[] nums = {2, 7, 9, 3, 1};
//        int k = 2;

        // 20
        int[] nums = {9, 6, 20, 21, 8};
        int k = 3;

        // 2
//        int[] nums = Utils.getArr(1000, 1, 10000);
//        int k = 300;

        int i = test.minCapability(nums, k);
        System.out.println(i);
    }

    public int minCapability(int[] nums, int k) {
        int st = Integer.MAX_VALUE;
        int end = 0;
        for (int num : nums) {
            st = Math.min(st, num);
            end = Math.max(end, num);
        }
        while (st < end) {
            boolean f = false;
            int m = st + ((end - st) >> 1);
            int count = 0;
            for (int num : nums) {
                if (num > m) {
                    f = false;
                } else {
                    if (!f) {
                        count++;
                    }
                    f = !f;
                }
            }
            if (count >= k) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
